package demo;

import java.util.Arrays;

public class SelectSort {
    //交换数组中两个位置的元素的值
    private static void swap(int[]array,int i,int j ){
        int temp=array[i];
        array[i]=array[j];
        array[j]=temp;
    }
    // 选择排序
    //每次找出无序区间里最大的元素下表，放到无序区间的最后
     public static void selectSort(int[] array) {
       int size=array.length;
       for(int i=0;i<size-1;i++){
           int mxaIdx=0;
           for(int j=1;j<size-i;j++){
               if(array[j]>array[mxaIdx]){
                   mxaIdx=j;
               }
           }
           swap(array,mxaIdx,size-i-1);

         }
     }
    //每次找到无序区间里最小的，放到无序区间开始
    public static void selectSort2(int[] array){
        int size= array.length;;
        for(int i=0;i<size-1;i++){
            //有序[0,i）
            //无序[i，size)
            //有序区间的最后 [i]
            int minIdx=i;
            for(int j=i+1;j<size;j++){
                if(array[j]<array[minIdx]){
                    minIdx=j;
                }
            }
            swap(array,i,minIdx);
        }

    }




    // 堆排序
       public static void heapSort(int[] array){
        createHeap(array);
        for(int i=0;i<array.length;i++){
            swap(array,0,array.length-1-i);
            shiftDown2(array, array.length-1-i,0);
        }
    }




    //向下调整(最小堆)
    public static void shiftDown(int[]array,int size,int index) {
        while (true) {
            int leftIdx = 2 * index + 1;

            if (leftIdx >= size) {
                return;
            }
            int minIdx = leftIdx;

            if (leftIdx + 1 < size && array[leftIdx + 1] < array[leftIdx]) {
                minIdx = leftIdx + 1;
            }

            if (array[minIdx] > array[index]) {
                return;
            }

            swap(array, minIdx, index);
            index = minIdx;


        }


    }
    //最大堆向下调整
        public static void shiftDown2(int[]array,int size,int index){

        while(true){
          int leftIdx=2*index+1;
          if(leftIdx>=size){
              return;
          }
          int maxIdx=leftIdx;
          if(leftIdx+1<size&&array[leftIdx+1]>array[leftIdx]){
              maxIdx=leftIdx+1;
          }
          if(array[maxIdx]<=array[index]){
              return ;
          }
          swap(array,maxIdx,index);
          index=maxIdx;
       }
        }


        //创建堆
        public static void createHeap(int[]array){
        int size=array.length;
        //创建堆需要从倒数第一个根结点开始向下调整
        int i=(size-1-1)/2;
        for(;i>=0;i--){
            //创建最大堆
            shiftDown2(array,array.length,i);
        }
        }


        public static void main (String[]args){
            int[] arr = {1, 9, 5, 7, 1, 5, 8, 0, 99};
            selectSort(arr);
            System.out.println("选择排序："+Arrays.toString(arr));


            int[] arr2 = {27, 15, 19, 18, 28, 34, 65, 49, 25, 37};
            shiftDown(arr2, 0,arr2.length);
            System.out.println("向下调整："+Arrays.toString(arr2));

            int[]arr3={8,4,6,5,1,3};
            createHeap(arr3);
            System.out.println("创建堆："+Arrays.toString(arr3));

            int[]arr4={1,0,9,55,4,5,8,3};
            heapSort(arr4);
            System.out.println("堆排序"+Arrays.toString(arr4));

        }

}
